﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AdapterSample
{
    class Adapter
    {
    }

    public interface ScoreOperation
    {
        int[] Sort(int[] array);
        int Search(int[] array, int key);
    }

    public class OperationAdapter:ScoreOperation   //适配者类
    {
        private QuickSortClass sortObj;
        private BinarySerachClass searchObj;
        public OperationAdapter ()
        {
            sortObj = new QuickSortClass();
            searchObj = new BinarySerachClass();
        }
        public int[] Sort(int[] array)
        {
            return sortObj.QuickSort(array);
        }
        public int Search(int[] array,int key)
        {
            return searchObj.BinarySearch(array,key);
        }
    }
    /// <summary>
    ///   二分法排序
    /// </summary>
    public class QuickSortClass
    {
        public int[] QuickSort(int[] array)
        {
            Sort(array, 0, array.Length - 1);
            return array;
        }

        public void Sort(int[] array, int p, int r)
        {
            int q = 0;
            if(p<r)
            {
                q = Partition(array, p, r);
                Sort(array, p, q - 1);
                Sort(array, q + 1, r);
            }
        }

        public int Partition(int[] a, int p, int r)
        {
            int x = a[r];
            int j = p - 1;
            for (int i = p; i <= r - 1; i++)
            { 
                if(a[i]<=x)
                {
                    j++;
                    Swap(a, j, i);
                }
            }
            Swap(a,j+1,r);
            return j+1;
        }

        public void Swap(int[] a, int i, int j)
        {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
  
    /// <summary>
    /// 二分法查询
    /// </summary>
    public class BinarySerachClass
    {
        public int BinarySearch(int[] array, int key)
        {
            int low = 0;//定义数组起始值
            int high = array.Length - 1;//定义数组最大长度 
            while(low<=high)   //在最小值和最大值之间遍历
            {
                int mid = (low + high)/2;
                int midVal = array[mid];  //获取中间值
                if(midVal<key)  //比较中间值与目标值的大小
                {
                    low = mid + 1;

                }
                else if(midVal>key)
                {
                    high = mid - 1;

                }
                else
                {
                    return 1;
                }
              

            }
            return -1;
        }
    }

}
